1. Field of the Invention
The present invention relates generally to convolutional encoders for modems. More particularly, the present invention relates to rotationally invariant convolutional encoders of modems capable of implementing a sixty-four state convolutional code which will support a four-to-five trellis code.
2. State of the Art
It is well known in the modem arts how to increase the signal to noise ratio of a modem by encoding bits of data which are to be modulated and sent over a telecommunications channel. In the encoding of bits, it has become relatively standard to employ a Trellis encoder. The Trellis encoder typically comprises a convolutional encoder and a mapper. Briefly, the convolutional encoder is a state update machine which receives inputs and generates outputs as a function of the inputs and/or the state of the machine at the time. In addition to generating outputs, the state update machine updates its state. Generally, the outputs of the convolutional encoder number one more than the inputs, thereby providing a redundancy which helps increase the signal-to-noise ratio of the system. The mapper receives as inputs the outputs of the convolutional encoder as well as other bits, and maps those inputs to one or more constellation points from which modulated signals are generated. When the mapper generates a single x,y constellation point value from the inputs, the system is said to be a two dimensional (2D) system. When the mapper generates two x,y constellation point values from the inputs, the system is said to be a four dimensional (4D) system, with the concatenation of the two x,y constellation points constituting a single point in a 4D "constellation".
Much attention has recently been paid to the code which is used in the convolutional encoder, as the code can effect the signal-to-noise ratio. The code of the convolutional encoder may be defined by the states of the convolutional encoder as connected by the outputs, or equivalently, the outputs of the convolutional encoder as connected by the states. Regardless, various different codes are known in the art. For example, a sixteen state, 4D code, a sixty-four state, 8D code, and a sixty-four state 4D code are described in U.S. Pat. No. 4,713,817 to Wei which is hereby incorporated by reference herein in its entirety. The sixty-four state, 4D code known as the "Wei code" as described in U.S. Pat. No. 4,713,817 was at one time proposed as the code for the new V.34 (V.fast) standard.
In the case of 4D codes, the mapper inputs taken from the convolutional encoder are used to select a subset within a four dimensional (4D) constellation. The other mapper inputs select a 4D constellation point within the 4D subset. These 4D subsets are predefined in terms of a partitioning of the 2D constellation points, with the sixteen state code employing eight 4D subsets derived from a four-way 2D partitioning, and the sixty-four state code employing thirty-two 4D subsets derived from an eight-way 2D partitioning obtained by splitting each set in the 4 way partitioning. These 4D subsets are labeled by three bit words and five bit words respectively.
With the 4D subsets and their labeling specified, it remains to define a convolutional encoder. The redundant bit inserted by the convolutional encoder doubles the number of 4D constellation points required for transmitting a given number of data bits per 4D point. The efficacy of Trellis encoding is based upon the premise that this redundancy penalty is exceeded substantially by an increased separation between the sequence of 4D points generated by the Trellis encoder. The convolutional encoder, which generates only some and not all possible sequences, provides this separation. The extent to which the separation provided by the convolutional encoder exceeds the redundancy penalty is the main measure of its performance with the Trellis encoder employing it.
All Trellis codes described in U.S. Pat. No. 4,713,817 to Wei have the following property, known as 90.degree. rotational invariance: the 0.degree., 90.degree., 180.degree. and 270.degree. rotation about the origin of any sequence of points generated by the Trellis encoder is itself a sequence of points generated by the Trellis encoder. In modem applications, rotational invariance is important because channel impairments can lead to phase ambiguities in the receiver. The rotations about the origin taking the thirty-two 4D subsets employed by the sixty-four state code to each other are 0.degree., 90.degree., 180.degree., 270.degree., and the same is true for the eight 4D subsets employed by the sixteen state code. So, a Trellis encoder employing of these collections of 4D subsets is rotationally invariant if and only if the convolutional encoder employed has the corresponding rotational invariance property.
The construction of rotationally invariant Trellis codes providing good separation between sequences is taught by U.S. Pat. No. 4,713,817 to Wei. It is the case, however, that the sixty-four state 4D code described in the Wei patent does not provide the separation between sequences suggested by the patent. In particular, the convolutional encoder employed in U.S. Pat. No. 4,713,817 to Wei is quasi-catastrophic; i.e., it fails to provide the property that any two sequences emerging from the same state must eventually merge into the same state, or else the separation between the two sequences becomes arbitrarily large. A convolutional encoder which provides this property is said to be non-quasi-catastrophic. While quasi-catastrophic codes can generally function without negatively affecting the output of the modem, it is theoretically possible that a sequence of inputs could cause a failure in the modem. Thus, it is desirable to utilize codes which are non-quasi-catastrophic.